Boolean valuation is an algorithmic process that, given a collection of literals comprising an input instance, identifies a satisfied subset of logical conjunctions in a previously defined set of conjunctions. A literal represents, inter alia, a symbol, word, phrase or proposition that may either be TRUE or FALSE. A conjunction, product, or AND-clause, is a set of literals where each literal is separated, either implicitly or explicitly, by an AND operator. A conjunction is said to be satisfied (i.e., TRUE) if all literals in the clause are TRUE. Any input instance satisfies zero or more conjunctions among a previously defined set of conjunctions. Such a previously defined set is also known as a rule set. A rule set can take the form of a set of sum of products Boolean expressions. In such a form, each sum-of-products expression maps to the same result, concept, class label or conclusion.
Conventional techniques for Boolean valuation have generally fallen into one of several broad classes: 1) heuristic approaches that are typically implemented by way of if-then statements in computer program code, 2) binary decision diagrams (BDDs), 3) trie data structures, and 4) hypergraph-based approaches. A choice of desirable technique may depend on rule set properties such as scale, sparseness, ordering, and clustering of data structures for input, lexicon, and results.